package leetcode每日一题;

/**
 * 1. 问题描述
 *
 * 2. 算法分析
 *
 * 3. 代码实现
 */
class ListNode{
    int val;
    ListNode next;
    ListNode(int val) {this.val = val;}
}
@SuppressWarnings("all")
public class 分隔链表 {
    public static void main(String[] args) {


    }

    public static ListNode partition(ListNode head, int x) {
        ListNode head1 = new ListNode(0);
        ListNode head2 = new ListNode(0);
        ListNode cur1 = head1;
        ListNode cur2 = head2;
        while(head != null) {
            if(head.val < x) {
                cur1.next = head; // 将head1挂到head链表上
                head = head.next; // head后移
                cur1 = cur1.next; // cur1后移
                cur1.next = null;
            } else {
                cur2.next = head;
                head = head.next;
                cur2 = cur2.next;
                cur2.next = null;
            }
        }
        cur1.next = head2.next;
        return head1.next;
    }
}
